//题目:
// 有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
// 你也被给予三个整数sr,sc和newColor。你应该从像素image[sr][sc]开始对图像进行上色填充 。
// 为了完成 上色工作,从初始像素开始,记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，
// 接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。
// 将所有有记录的像素点的颜色值改为 newColor 。
// 最后返回 经过上色渲染后的图像 。
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
//代码:
class Solution 
{
public:
    void walk_maze(vector<vector<pair<bool,int>>>& vv,vector<pair<int,int>>& v, int sr, int sc)
    {
        //1.能进入这个函数，说明[sr][sc]这个位置本身就是“可行走的”
        v.push_back(make_pair(sr,sc));//把自己的位置给记下来
        vv[sr][sc].first=true;//修改自身位置的属性标识

        //2.判断上路是否可走
        if(sr-1>=0 && vv[sr-1][sc].second==vv[sr][sc].second && vv[sr-1][sc].first==false)
        {
            //说明自身与上路是相连通的，且上路“没被洪水淹过”
            walk_maze(vv,v,sr-1,sc);//去上路
        }

        //3.判断下路是否可走
        if(sr+1<vv.size() && vv[sr+1][sc].second==vv[sr][sc].second && vv[sr+1][sc].first==false)
        {
            //说明自身与下路是相连通的，且下路“没被洪水淹过”
            walk_maze(vv,v,sr+1,sc);//去下路
        }

        //4.判断左路是否可走
        if(sc-1>=0 && vv[sr][sc-1].second==vv[sr][sc].second && vv[sr][sc-1].first==false)
        {
            //说明自身与左路是相连通的，且左路“没被洪水淹过”
            walk_maze(vv,v,sr,sc-1);//去左路
        }

        //5.判断右路是否可走
        if(sc+1<vv[0].size() && vv[sr][sc+1].second==vv[sr][sc].second && vv[sr][sc+1].first==false)
        {
            //说明自身与右路是相连通的，且右路“没被洪水淹过”
            walk_maze(vv,v,sr,sc+1);//去右路
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        //法一(dfs深度优先遍历，递归法):
        //1.建立一个存放结果的容器
        // vector<pair<int,int>> v;//存放所有符合条件的像素点坐标
        // v.push_back(make_pair(sr,sc));
        // //2.给每个坐标赋予一个标识
        // vector<vector<pair<bool,int>>> vv(image.size());//key表示每个坐标是否被“洪水经过”,value代表坐标值
        // for(int i=0;i<image.size();i++)
        // {
        //     vv[i].resize(image[i].size());
        //     for(int j=0;j<image[i].size();j++)
        //     {
        //         vv[i][j]=make_pair(false,image[i][j]);
        //     }
        // }
        // //3.从image[sr][sc]开始“走迷宫”，并收集“可行走的位置”，直到无路可走
        // walk_maze(vv,v,sr,sc);
        // //4.上色
        // for(int i=0;i<v.size();i++)
        // {
        //     int x=v[i].first;
        //     int y=v[i].second;
        //     image[x][y]=color;
        // }
        // //5.返回结果
        // return image;

        //法二(bfs宽度优先遍历，队列法):
        int arrx[]={-1,1,0,0},arry[]={0,0,-1,1};//上下左右

        queue<pair<int,int>> q;//存放元素坐标
        int goal=image[sr][sc];//记录初始目标值
        if(goal==color)return image;
        q.push(make_pair(sr,sc));
        while(!q.empty())
        {
            //同层坐标出队列，并完成像素渲染
            pair<int,int> pir=q.front();
            q.pop();
            image[pir.first][pir.second]=color;//像素渲染
            //上下左右相邻坐标入队列    
            for(int i=0;i<4;i++)
            {
                int x=pir.first+arrx[i],y=pir.second+arry[i];
                if(x>=0 && x<image.size() && y>=0 && y<image[0].size() && image[x][y]==goal)
                {
                    q.push(make_pair(x,y));
                }
            }
        }
        return image;
    }
};